package ADD_project;
import java.util.Arrays;
public class KnapsackProblem {
    static class Item {
        int weight;
        int value;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    // 使用贪心算法求解01背包问题
    public static int knapsack(Item[] items, int w) {
        // 按照单位重量价值从高到低排序
        Arrays.sort(items, (i1, i2) -> Double.compare((double)i2.value / i2.weight, (double)i1.value / i1.weight));

        int n = items.length;
        int maxVal = 0;
        for (int i = 0; i < n && w > 0; i++) {
            if (w >= items[i].weight) {
                // 可以将整个物品放入背包中
                maxVal += items[i].value;
                w -= items[i].weight;
            } else {
                // 只能将部分物品放入背包中
                maxVal += (int)((double)w / items[i].weight * items[i].value);
                w = 0;
            }
        }
        return maxVal;
    }

    public static void main(String[] args) {
        Item[] items = {new Item(2, 3), new Item(12, 30), new Item(40, 50), new Item(5, 1), new Item(12, 10), new Item(3, 4)};
        int w = 50;
        int maxVal = knapsack(items, w);
        System.out.println(maxVal); // 输出：80
    }
}
